COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00005 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a21.tex[154,phy] \today\hfill}

\parskip5pt
\parindent0pt
\bigskip
\noindent{\bf (2) Exercise:} In the graph with nodes $\{1,2,3,4\}$, the edges,
labeled, are:
$$\vcenter{\halign{$\ctr{#}$\quad&$\ctr{#}$\quad&$\ctr{#}$\cr
1&a&2\cr
2&b&3\cr
3&c&4\cr
4&d&1\cr
1&e&4\cr
4&f&3\cr
3&g&2\cr
2&h&1\cr}}$$
Give a regular expression for the labels of all paths from 1 to~3.

$$\vcenter{\halign{$\ctr{#}$\quad&$\ctr{#}$\quad&$\ctr{#}$\quad%
&$\ctr{#}$\quad&$\ctr{#}$\quad&$\ctr{#}$\quad&$\ctr{#}$\cr
&&&a\cr
\noalign{\smallskip}
&1&&&&2\cr
\noalign{\smallskip}
&&&h\cr
\noalign{\medskip}
d&&e&&g&&b\cr
\noalign{\medskip}
&&&f\cr
\noalign{\smallskip}
&4&&&&3\cr
\noalign{\smallskip}
&&&c\cr}}$$

\bigskip\noindent
{\bf (3)} Hopcroft Ullman 2.17.

\bigskip\noindent
{\bf (4)} Hopcroft Ullman 2.20.

Hint: First consider the corresponding problems for 2DFA.

\bigskip
\noindent
Due: Wednesday, April 23, 1986.



\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft October 16, 1984

\bye